{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Make Array Sum At Most x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组和小于等于 x 的最少时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度相等下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;。每一秒，对于所有下标&nbsp;<code>0 &lt;= i &lt; nums1.length</code>&nbsp;，<code>nums1[i]</code>&nbsp;的值都增加&nbsp;<code>nums2[i]</code>&nbsp;。操作&nbsp;<strong>完成后</strong>&nbsp;，你可以进行如下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择任一满足&nbsp;<code>0 &lt;= i &lt; nums1.length</code>&nbsp;的下标 <code>i</code>&nbsp;，并使&nbsp;<code>nums1[i] = 0</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>同时给你一个整数&nbsp;<code>x</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回使&nbsp;<code>nums1</code>&nbsp;中所有元素之和 <strong>小于等于</strong>&nbsp;<code>x</code>&nbsp;所需要的 <strong>最少</strong>&nbsp;时间，如果无法实现，那么返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,2,3], nums2 = [1,2,3], x = 4\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>\n",
    "第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。\n",
    "第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。\n",
    "第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。\n",
    "现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,2,3], nums2 = [3,3,3], x = 4\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>不管如何操作，nums1 的和总是会超过 x 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length &lt;= 10<sup>3</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i] &lt;= 10<sup>3</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums2[i] &lt;= 10<sup>3</sup></code></li>\n",
    "\t<li><code>nums1.length == nums2.length</code></li>\n",
    "\t<li><code>0 &lt;= x &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-make-array-sum-at-most-x](https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-make-array-sum-at-most-x](https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n[1,2,3]\\n4', '[1,2,3]\\n[3,3,3]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power.sort()\n",
    "        N = len(power)\n",
    "        MAXP = power[-1]\n",
    "        queue = [(int(ceil(sum(power[i - 1] / i for i in range(1, N + 1)))), 0, 0, 0)]\n",
    "        current_min = {0: 0}\n",
    "        def _ceildiv(x, y):\n",
    "            return (x + y - 1) // y\n",
    "\n",
    "        while queue:\n",
    "            _, mask, selected, total = heappop(queue)\n",
    "            if mask == ((1 << N) - 1):\n",
    "                return total\n",
    "            if current_min[mask] < total:\n",
    "                continue\n",
    "            upper_bound = MAXP\n",
    "            last_try = 0\n",
    "            a = selected + 1\n",
    "            for j in range(N):\n",
    "                if not ((1 << j) & mask):\n",
    "                    if power[j] > upper_bound:\n",
    "                        break\n",
    "                    # 剪枝1：重复的数字只按照从前往后的顺序匹配\n",
    "                    if power[j] == last_try:\n",
    "                        continue\n",
    "                    last_try = power[j]\n",
    "                    next_total = total + _ceildiv(power[j], a)\n",
    "                    next_mask = (mask | (1 << j))\n",
    "                    # 剪枝2：选中相同集合时只保留最佳答案（类似状态压缩DP）\n",
    "                    if next_mask in current_min and current_min[next_mask] <= next_total:\n",
    "                        continue\n",
    "                    current_min[next_mask] = next_total\n",
    "                    # A*估值函数：利用sum(ceil(a/b)) >= ceil(sum(a/b))\n",
    "                    estimate = next_total + \\\n",
    "                        int(ceil(sum(p / k for p, k in zip(\n",
    "                            (p for l, p in enumerate(power)\n",
    "                                if not ((1 << l) & next_mask)),\n",
    "                            range(a + 1, N + 1)\n",
    "                        ))))\n",
    "                    heappush(queue, (estimate, next_mask, selected + 1, next_total))\n",
    "                    # 剪枝3：需要尝试的数值可以被限定在一个较小的范围内\n",
    "                    current_upper = 0\n",
    "                    m = power[j]\n",
    "                    for b in range(a + 1, N + 1):\n",
    "                        est_upper = (_ceildiv(m, a) * a * b - a * (m+1)) // (b-a)\n",
    "                        if est_upper <= current_upper:\n",
    "                            break\n",
    "                        real_upper = ((_ceildiv(m, a) - _ceildiv(m, b)) * a * b - a) // (b - a)\n",
    "                        current_upper = max(current_upper, real_upper)\n",
    "                        if current_upper >= upper_bound:\n",
    "                            break\n",
    "                    upper_bound = min(current_upper, upper_bound)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from math import ceil\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power.sort()\n",
    "        N = len(power)\n",
    "        MAXP = power[-1]\n",
    "        queue = [(int(ceil(sum(power[i - 1] / i for i in range(1, N + 1)))), 0, 0, 0)]\n",
    "        current_min = {0: 0}\n",
    "\n",
    "        def _ceildiv(x, y):\n",
    "            return (x + y - 1) // y\n",
    "\n",
    "        while queue:\n",
    "            _, mask, selected, total = heappop(queue)\n",
    "            if mask == ((1 << N) - 1):\n",
    "                return total\n",
    "            if current_min[mask] < total:\n",
    "                continue\n",
    "\n",
    "            upper_bound = MAXP\n",
    "            last_try = 0\n",
    "            a = selected + 1\n",
    "            for j in range(N):\n",
    "                if not ((1 << j) & mask):\n",
    "                    if power[j] > upper_bound:\n",
    "                        break\n",
    "                    if power[j] == last_try:\n",
    "                        continue\n",
    "                    last_try = power[j]\n",
    "\n",
    "                    next_total = total + _ceildiv(power[j], a)\n",
    "                    next_mask = (mask | (1 << j))\n",
    "                    if next_mask in current_min and current_min[next_mask] <= next_total:\n",
    "                        continue\n",
    "\n",
    "                    current_min[next_mask] = next_total\n",
    "                    estimate = next_total + int(ceil(sum(p / k for p, k in zip(\n",
    "                        (p for l, p in enumerate(power) if not ((1 << l) & next_mask)),\n",
    "                        range(a + 1, N + 1)\n",
    "                    ))))\n",
    "                    heappush(queue, (estimate, next_mask, selected + 1, next_total))\n",
    "                    \n",
    "                    current_upper = 0\n",
    "                    m = power[j]\n",
    "                    for b in range(a + 1, N + 1):\n",
    "                        est_upper = (_ceildiv(m, a) * a * b - a * (m+1)) // (b-a)\n",
    "                        if est_upper <= current_upper:\n",
    "                            break\n",
    "                        real_upper = ((_ceildiv(m, a) - _ceildiv(m, b)) * a * b - a) // (b - a)\n",
    "                        current_upper = max(current_upper, real_upper)\n",
    "                        if current_upper >= upper_bound:\n",
    "                            break\n",
    "                    upper_bound = min(current_upper, upper_bound)\n",
    "\n",
    "# 示例\n",
    "s = Solution()\n",
    "print(s.minimumTime([3, 5, 7]))  # 输出应该是天数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power.sort()\n",
    "        N = len(power)\n",
    "        MAXP = power[-1]\n",
    "        queue = [(int(ceil(sum(power[i - 1] / i for i in range(1, N + 1)))), 0, 0, 0)]\n",
    "        current_min = {0: 0}\n",
    "        def _ceildiv(x, y):\n",
    "            return (x + y - 1) // y\n",
    "\n",
    "        while queue:\n",
    "            _, mask, selected, total = heappop(queue)\n",
    "            if mask == ((1 << N) - 1):\n",
    "                return total\n",
    "            if current_min[mask] < total:\n",
    "                continue\n",
    "            upper_bound = MAXP\n",
    "            last_try = 0\n",
    "            a = selected + 1\n",
    "            for j in range(N):\n",
    "                if not ((1 << j) & mask):\n",
    "                    if power[j] > upper_bound:\n",
    "                        break\n",
    "                    # 剪枝1：重复的数字只按照从前往后的顺序匹配\n",
    "                    if power[j] == last_try:\n",
    "                        continue\n",
    "                    last_try = power[j]\n",
    "                    next_total = total + _ceildiv(power[j], a)\n",
    "                    next_mask = (mask | (1 << j))\n",
    "                    # 剪枝2：选中相同集合时只保留最佳答案（类似状态压缩DP）\n",
    "                    if next_mask in current_min and current_min[next_mask] <= next_total:\n",
    "                        continue\n",
    "                    current_min[next_mask] = next_total\n",
    "                    # A*估值函数：利用sum(ceil(a/b)) >= ceil(sum(a/b))\n",
    "                    estimate = next_total + \\\n",
    "                        int(ceil(sum(p / k for p, k in zip(\n",
    "                            (p for l, p in enumerate(power)\n",
    "                                if not ((1 << l) & next_mask)),\n",
    "                            range(a + 1, N + 1)\n",
    "                        ))))\n",
    "                    heappush(queue, (estimate, next_mask, selected + 1, next_total))\n",
    "                    # 剪枝3：需要尝试的数值可以被限定在一个较小的范围内\n",
    "                    current_upper = 0\n",
    "                    m = power[j]\n",
    "                    for b in range(a + 1, N + 1):\n",
    "                        est_upper = (_ceildiv(m, a) * a * b - a * (m+1)) // (b-a)\n",
    "                        if est_upper <= current_upper:\n",
    "                            break\n",
    "                        real_upper = ((_ceildiv(m, a) - _ceildiv(m, b)) * a * b - a) // (b - a)\n",
    "                        current_upper = max(current_upper, real_upper)\n",
    "                        if current_upper >= upper_bound:\n",
    "                            break\n",
    "                    upper_bound = min(current_upper, upper_bound)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power = sorted(power)\n",
    "        gain = 1\n",
    "\n",
    "        n = len(power)\n",
    "        x = power[0]\n",
    "        visited = [0]*n\n",
    "        visited[0] = 1\n",
    "\n",
    "        m = n-1\n",
    "        full_mask = 1<<m\n",
    "        dp = [float(\"inf\")]*(1<<m)\n",
    "        dp[0] = power[0]\n",
    "        \n",
    "        for mask in range(1,full_mask):\n",
    "            for j in range(m):\n",
    "                if mask & (1<<j)==0:\n",
    "                    continue \n",
    "                count = mask.bit_count()\n",
    "                gain = 1+count\n",
    "                x = (power[j+1]//gain)+1 if power[j+1]%gain else power[j+1]//gain\n",
    "                dp[mask] = min(dp[mask], dp[mask ^(1<<j)]+x)\n",
    "        \n",
    "        return dp[full_mask-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n=len(power)\n",
    "        dp=[0]*(1<<n)\n",
    "        for i in range(1,1<<n):\n",
    "            c=0\n",
    "            tp=[]\n",
    "            for j in range(n):\n",
    "                if i&(1<<j):\n",
    "                    c+=1\n",
    "                    tmp=i^(1<<j)\n",
    "                    tp.append([j,tmp])\n",
    "            dp[i]=min(dp[tmp]+math.ceil(power[j]/c) for j,tmp in tp)\n",
    "        #print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        dp = [float('inf') ] *(1 << n)\n",
    "        dp[0] = 0 \n",
    "        def gain(x):\n",
    "            g = 1\n",
    "            for i in range(n):\n",
    "                if (x >> i) & 1:\n",
    "                    g+=1\n",
    "            return g \n",
    "\n",
    "        for i in range(1<<n):\n",
    "            g = gain(i)\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1 == 0:\n",
    "                    dp[i | (1 << j)] = min(dp[i | (1 << j)], dp[i]+(power[j] + g - 1)//g)\n",
    "        \n",
    "        return dp[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \n",
    "        start_gain = 1\n",
    "        n = len(power)\n",
    "        dp = [10**11]*(1<<n)\n",
    "        dp[0] = 0\n",
    "        for mask in range(1<<n):\n",
    "            gain = start_gain-1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    gain += 1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    dp[mask] = min(dp[mask],dp[mask - (1<<i )] + ( power[i] + gain - 1) //gain ) \n",
    "            \n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        powers = power.copy()\n",
    "        power = []\n",
    "        ans = 0\n",
    "        for p in powers:\n",
    "            if p==1:\n",
    "                ans += 1\n",
    "            else:\n",
    "                power.append(p)\n",
    "        start_gain = 0\n",
    "        if ans :\n",
    "            powers = power.copy()\n",
    "            power = []\n",
    "            for p in powers:\n",
    "                if p==2:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    power.append(p)\n",
    "            start_gain = ans + 1\n",
    "        else:\n",
    "            powers = power.copy()\n",
    "            power = []\n",
    "            for p in powers:\n",
    "                if p==2:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    power.append(p)\n",
    "            start_gain = ans + 1 \n",
    "             \n",
    "            if ans:\n",
    "                ans += 1\n",
    "           \n",
    "\n",
    "        \n",
    "        n = len(power)\n",
    "        dp = [10**11]*(1<<n)\n",
    "        dp[0] = 0\n",
    "        for mask in range(1<<n):\n",
    "            gain = start_gain-1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    gain += 1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    dp[mask] = min(dp[mask],dp[mask - (1<<i )] + ( power[i] + gain - 1) //gain ) \n",
    "            \n",
    "        return dp[-1] + ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        powers = power.copy()\n",
    "        power = []\n",
    "        ans = 0\n",
    "        for p in powers:\n",
    "            if p==1:\n",
    "                ans += 1\n",
    "            else:\n",
    "                power.append(p)\n",
    "\n",
    "        if ans :\n",
    "            powers = power.copy()\n",
    "            power = []\n",
    "            for p in powers:\n",
    "                if p==2:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    power.append(p)\n",
    "\n",
    "\n",
    "        start_gain = ans + 1\n",
    "        n = len(power)\n",
    "        dp = [10**11]*(1<<n)\n",
    "        dp[0] = 0\n",
    "        for mask in range(1<<n):\n",
    "            gain = start_gain-1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    gain += 1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    dp[mask] = min(dp[mask],dp[mask - (1<<i )] + ( power[i] + gain - 1) //gain ) \n",
    "            \n",
    "        return dp[-1] + ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        dp = [float('inf') for _ in range(1 << n)]\n",
    "        dp[0] = 0 \n",
    "        def gain(x):\n",
    "            g = 1\n",
    "            for i in range(n):\n",
    "                if (x >> i) & 1:\n",
    "                    g+=1\n",
    "            return g \n",
    "\n",
    "        for i in range(1<<n):\n",
    "            g = gain(i)\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1 == 0:\n",
    "                    dp[i | (1 << j)] = min(dp[i | (1 << j)], dp[i]+(power[j] + g - 1)//g)\n",
    "        \n",
    "        return dp[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n=len(power)\n",
    "        dp=[0]*(1<<n)\n",
    "        for i in range(1,1<<n):\n",
    "            c=0\n",
    "            tp=[]\n",
    "            for j in range(n):\n",
    "                if i&(1<<j):\n",
    "                    c+=1\n",
    "                    tmp=i^(1<<j)\n",
    "                    tp.append([j,tmp])\n",
    "            dp[i]=min(dp[tmp]+math.ceil(power[j]/c) for j,tmp in tp)\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n=len(power)\n",
    "        dp = [{} for j in range(n+1)]\n",
    "        dp[0][0]=0 \n",
    "\n",
    "        for cnt in range(1,n+1):\n",
    "            for i,mon in enumerate(power):\n",
    "                for olds in dp[cnt-1]:\n",
    "                    s=olds|1<<i\n",
    "                    if s==olds:\n",
    "                        continue\n",
    "                    dps=dp[cnt-1][olds]+(mon-1)//cnt+1\n",
    "\n",
    "                    if s not in dp[cnt] or dp[cnt][s]>dps:\n",
    "                        dp[cnt][s]=dps\n",
    "        \n",
    "        return dp[-1][(1<<n)-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTime(self, power: List[int]) -> int:\r\n",
    "\r\n",
    "        dp = [{} for j in range(len(power)+1)]\r\n",
    "        dp[0][0]=0  #边界条件\r\n",
    "        for cur in range(1,len(power)+1): #遍历打怪数量\r\n",
    "            for j,choose in enumerate(power): # 遍历当前选择的怪物\r\n",
    "                for ls in dp[cur-1]: #遍历上一层的所有状态\r\n",
    "                    s = ls|(1<<j)\r\n",
    "                    if s==ls: #这说明当前这只怪物打过了，跳过\r\n",
    "                        continue\r\n",
    "                    dps = dp[cur-1][ls]+(choose-1)//cur+1 # 注意当前怪物需要天数不能直接用整除，但可以直接调math.ceil\r\n",
    "                    if s not in dp[cur] or dp[cur][s]>dps: # s首次出现或者找到一个更优值时更新\r\n",
    "                        dp[cur][s]=dps\r\n",
    "        \r\n",
    "        return dp[-1][(1<<(len(power)))-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "\n",
    "        dp = [{} for j in range(len(power)+1)]\n",
    "        dp[0][0]=0  #边界条件\n",
    "        for cur in range(1,len(power)+1): #遍历打怪数量\n",
    "            for j,choose in enumerate(power): # 遍历当前选择的怪物\n",
    "                for ls in dp[cur-1]: #遍历上一层的所有状态\n",
    "                    s = ls|(1<<j)\n",
    "                    if s==ls: #这说明当前这只怪物打过了，跳过\n",
    "                        continue\n",
    "                    dps = dp[cur-1][ls]+(choose-1)//cur+1 # 注意当前怪物需要天数不能直接用整除，但可以直接调math.ceil\n",
    "                    if s not in dp[cur] or dp[cur][s]>dps: # s首次出现或者找到一个更优值时更新\n",
    "                        dp[cur][s]=dps\n",
    "        \n",
    "        return dp[-1][(1<<(len(power)))-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        '''\n",
    "        打倒怪物的顺序会影响到最终的答案\n",
    "        所以，直接枚举所有怪物被击杀的顺序\n",
    "        f[i][mask]前i次击杀，击杀的怪物集合为mask\n",
    "        f[i][mask]=枚举第i次击杀了第j个怪物，f[i-1][mask^(1<<j)]+cnt[i][j]\n",
    "        cnt[i][j]预处理在每天获得gain点能量的情况下，击杀第j个怪物的最短耗时\n",
    "        cnt[i][j]=math.ceil(power[j]/i)\n",
    "        '''\n",
    "        n=len(power)\n",
    "        MX=1<<n\n",
    "        f=[[inf]*MX for _ in range(n+1)] #总共需要n次击杀  \n",
    "        f[0][0]=0\n",
    "        for i in range(n):\n",
    "            for j in range(1,MX):\n",
    "                if j.bit_count()!=i+1:\n",
    "                    continue\n",
    "                for bit in range(n):\n",
    "                    if j>>bit&1:\n",
    "                        f[i+1][j]=min(f[i+1][j],f[i][j^(1<<bit)]+math.ceil(power[bit]/(i+1)))\n",
    "        return f[n][MX-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        @cache\n",
    "        def dfs(st):\n",
    "            k = st.bit_count()+1\n",
    "            if k==n+1:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if not st&1<<i:\n",
    "                    res = min(res,(power[i]-1)//k+1+dfs(st|1<<i))\n",
    "            return res\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        #状态压缩+记忆化搜索,1表示当前还未打败，0表示当前已打败\n",
    "        n=len(power)\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            if mask==0: return 0\n",
    "            bit=n-mask.bit_count()   #0的个数\n",
    "            res=inf\n",
    "            for i in range(n):\n",
    "                if mask>>i&1:\n",
    "                    res=min(res,dfs(mask^(1<<i))+ceil(power[i]/(1+bit)))\n",
    "            return res\n",
    "        return dfs((1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            cnt = mask.bit_count()\n",
    "            if cnt == n:\n",
    "                return 0\n",
    "            \n",
    "            ans = inf\n",
    "            for i in range(n):\n",
    "                cur = 1 << i\n",
    "                if mask & cur:\n",
    "                    continue\n",
    "                ans = min(ans, dfs(mask | cur) + ceil(power[i] / (cnt + 1)))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        #状态压缩+记忆化搜索,1表示当前还未打败，0表示当前已打败\n",
    "        n=len(power)\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            if mask==0: return 0\n",
    "            bit=n-mask.bit_count()   #0的个数\n",
    "            res=inf\n",
    "            for i in range(n):\n",
    "                if mask>>i&1:\n",
    "                    res=min(res,dfs(mask^(1<<i))+ceil(power[i]/(1+bit)))\n",
    "            return res\n",
    "        return dfs((1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTime(self, power: List[int]) -> int:\r\n",
    "        n = len(power)\r\n",
    "\r\n",
    "        @cache\r\n",
    "        def dfs(mask):\r\n",
    "            cnt = mask.bit_count()\r\n",
    "            if cnt == n:\r\n",
    "                return 0\r\n",
    "            \r\n",
    "            ans = inf\r\n",
    "            for i in range(n):\r\n",
    "                cur = 1 << i\r\n",
    "                if mask & cur:\r\n",
    "                    continue\r\n",
    "                ans = min(ans, dfs(mask | cur) + ceil(power[i] / (cnt + 1)))\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        @cache\n",
    "        def mDFS(mask):\n",
    "            if mask == ed: return 0\n",
    "            gain = mask.bit_count() + 1\n",
    "            res = inf\n",
    "            for k, x in enumerate(power):\n",
    "                if mask >> k & 1: continue\n",
    "                res = min(res, mDFS(mask | (1 << k)) + (x + gain - 1) // gain)\n",
    "            return res\n",
    "\n",
    "        ed = (1 << len(power)) - 1\n",
    "        return mDFS(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos):\n",
    "            if pos == (1 << n) - 1:\n",
    "                return 0\n",
    "            res = float('inf')\n",
    "            k = bin(pos).count('1')\n",
    "            for i in range(n):\n",
    "                if pos & (1 << i) == 0:\n",
    "                    res = min(res, dfs(pos | (1 << i)) + ceil(power[i] / (k + 1)))\n",
    "            return res\n",
    "        return dfs(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "            if pace > 10 * max1:\n",
    "                return math.inf\n",
    "            v1 = math.inf\n",
    "\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            #v1 = min(v1, 1 + get_min_time(pace+mana, mana, fz))\n",
    "            return v1\n",
    "\n",
    "\n",
    "\n",
    "        ret = get_min_time(0, 1, frozenset({}))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "            v1 = math.inf\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            return v1\n",
    "\n",
    "        return get_min_time(0, 1, frozenset({}))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "        \n",
    "            v1 = math.inf\n",
    "\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            #v1 = min(v1, 1 + get_min_time(pace+mana, mana, fz))\n",
    "            return v1\n",
    "\n",
    "\n",
    "\n",
    "        ret = get_min_time(0, 1, frozenset({}))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "            if pace > max1 + 2 * mana:\n",
    "                return math.inf\n",
    "            v1 = math.inf\n",
    "\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            #v1 = min(v1, 1 + get_min_time(pace+mana, mana, fz))\n",
    "            return v1\n",
    "\n",
    "\n",
    "\n",
    "        ret = get_min_time(0, 1, frozenset({}))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        numbers = sorted((n2, n1) for n1, n2 in zip(nums1, nums2))\n",
    "        N = len(numbers)\n",
    "        minSum = [0] * (N + 1)\n",
    "        s = 0\n",
    "        for i, (n2, n1) in enumerate(numbers):\n",
    "            minSum[i + 1] = minSum[i] + s\n",
    "            for j in range(i, 0, -1):\n",
    "                minSum[j] = min(minSum[j - 1] + s, minSum[j] + n1 + n2 * j)\n",
    "            minSum[0] += n1\n",
    "            s += n2\n",
    "        for j in range(N + 1):\n",
    "            if minSum[j] <= x:\n",
    "                return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minimumTime(self, nums1, nums2, x):\n",
    "\t\tn = len(nums1)\n",
    "\t\tadd = sum(nums2)\n",
    "\t\ttot = sum(nums1)\n",
    "\t\tif tot <= x:\n",
    "\t\t\treturn 0\n",
    "\t\tq = list(zip(nums2, nums1))\n",
    "\t\tq.sort()\n",
    "\t\tlast = [0] * n\n",
    "\t\tfor i in range(n): #进行i + 1次操作\n",
    "\t\t\ttot += add\n",
    "\t\t\tcur = [0] * (n + 1)\n",
    "\t\t\tfor j in range(i, n): #对下标0..j的元素操作\n",
    "\t\t\t\tcur[j] = max(cur[j - 1], q[j][1] + q[j][0] * (i + 1) + last[j - 1])\n",
    "\t\t\tif tot - max(cur) <= x:\n",
    "\t\t\t\treturn i + 1\n",
    "\t\t\tlast = cur\n",
    "\t\treturn -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n=len(nums1)\n",
    "        arr=list(range(n))\n",
    "        arr.sort(key=lambda x:nums2[x])\n",
    "        f=[0]*(n+1)\n",
    "        for i in arr:\n",
    "            for j in range(n,0,-1):\n",
    "                f[j]=max(f[j],f[j-1]+nums1[i]+j*nums2[i])\n",
    "        \n",
    "        s1=sum(nums1)\n",
    "        s2=sum(nums2)\n",
    "\n",
    "        for t,v in enumerate(f):\n",
    "            if s1+s2*t-v<=x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        f = [0] * (n+1)\n",
    "\n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda x : x[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j-1] + a + b * j)\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j - 1] + a + b * j)\n",
    "\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j - 1] + a + b * j)\n",
    "\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [0] * (n + 1) \n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda x: x[1]):\n",
    "            for j in range(n, 0, - 1):\n",
    "                dp[j] = max(dp[j], dp[j - 1] + a + b * j)\n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        for i in range(n + 1):\n",
    "            if s1 + s2 * i - dp[i] <= x:\n",
    "                return i \n",
    "        return - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for a,b in sorted(zip(nums1, nums2), key = lambda z: z[1]):\n",
    "            for j in range(n, 0 , -1):\n",
    "                f[j] = max(f[j], f[j-1] + a + b * j)\n",
    "\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j - 1] + a + b * j)\n",
    "\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for i, j in sorted(zip(nums1, nums2), key = lambda p: p[1]):\n",
    "            for t in range(n, 0, -1):\n",
    "                f[t] = max(f[t], f[t - 1] + i + j * t)\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t in range(n + 1):\n",
    "            if (s1 + s2 * t) - f[t] <= x:\n",
    "                return t\n",
    "        return -1\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "#         n = len(nums1)\n",
    "\n",
    "#         def judge(t, x):\n",
    "#             _sum = sum(nums1) + t * sum(nums2)\n",
    "#             w = int((t+1)*t / 2)\n",
    "\n",
    "#             bags = [[0] for _ in range(n)]\n",
    "#             for i in range(n):\n",
    "#                 for j in range(1, t+1):\n",
    "#                     bags[i].append(nums1[i] + j * nums2[i])\n",
    "\n",
    "#             dp = [[[0,0] for j in range(w + 1)] for i in range(n)]\n",
    "#             for j in range(t + 1):\n",
    "#                 dp[0][j][0] = bags[0][j]\n",
    "#                 dp[0][j][1] = 1\n",
    "#             dp[0][0][1] = 0\n",
    "#             for i in range(n):\n",
    "#                 for j in range(w, -1, -1):\n",
    "#                     for k in range(min(j, t) + 1):\n",
    "#                         if k > 0 and dp[i-1][j-k][1] + 1 <= t:\n",
    "#                             if dp[i][j][0] < dp[i-1][j-k][0] + bags[i][k]:\n",
    "#                                 dp[i][j][0] = max(dp[i][j][0], dp[i-1][j - k][0] + bags[i][k])\n",
    "#                                 dp[i][j][1] = dp[i-1][j-k][1] + 1\n",
    "#                             if dp[i][j][0] >= _sum - x:\n",
    "#                                 return True\n",
    "#             return False\n",
    "\n",
    "#         l, r = 0, n\n",
    "#         while(r-l > 1):\n",
    "#             mid = (l + r) >> 1\n",
    "#             if judge(mid, x):\n",
    "#                 r = mid\n",
    "#             else:\n",
    "#                 l = mid\n",
    "#         if judge(l, x):\n",
    "#             return l\n",
    "#         if judge(r, x):\n",
    "#             return r\n",
    "#         else:\n",
    "#             return -1\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j - 1] + a + b * j)\n",
    "\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "\n",
    "        N = len(nums1)\n",
    "        dp = [ 0 for _ in range(N+1) ] \n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "\n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda x : x[1]):\n",
    "            for j in range(N, 0, -1):\n",
    "                dp[j] = max(dp[j-1] + a + b * j, dp[j])\n",
    "\n",
    "        for t in range(N+1):\n",
    "            st = s1 + s2 * t\n",
    "            if st - dp[t] <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        g = sorted((j, i) for i, j in zip(nums1, nums2))\n",
    "        t1, t2 = sum(nums1), sum(nums2)\n",
    "        if t1 <= x: return 0\n",
    "        f = [t1] * (n + 1)\n",
    "        for j in range(1, n + 1):\n",
    "            h = [inf] * (n + 1)\n",
    "            h[j] = f[j - 1]\n",
    "            for i in range(j + 1, n + 1):\n",
    "                h[i] = min(h[i - 1], f[i - 1])\n",
    "            for i in range(j, n + 1):\n",
    "                # f[i] = min(f[k] for k in range(j - 1, i)) + t2 - g[i - 1][1] - j * g[i - 1][0]\n",
    "                f[i] = h[i] + t2 - g[i - 1][1] - j * g[i - 1][0]\n",
    "                if f[i] <= x: return j\n",
    "        return -1\n",
    "            \n",
    "\n",
    "        # @cache\n",
    "        # def f(i, j):\n",
    "        #     # 删除第i项，是第j次删除\n",
    "        #     if j == 0: return t1\n",
    "        #     return min(f(k, j - 1) for k in range(j - 1, i)) + t2 - g[i - 1][1] - j * g[i - 1][0]\n",
    "        # for j in range(n + 1):\n",
    "        #     if any(f(k, j) <= x for k in range(j, n + 1)): return j\n",
    "        # return -1 \n",
    "\n",
    "                \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 建议直接看答案；本题难度有点高\n",
    "# dp[i][j]的定义为nums2的前i个数字经过j秒对总和减值贡献最大的值；其中nums2为升序排序\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums2)\n",
    "        dp = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda x:x[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                dp[j] = max(dp[j], dp[j-1] + a + b * j)\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t in range(n+1):\n",
    "            s = s1 + s2 * t\n",
    "            if s - dp[t] <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [0] * (n + 1) \n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda x: x[1]):\n",
    "            new = dp[:]\n",
    "            for j in range(1, n + 1):\n",
    "                new[j] = max(new[j], dp[j - 1] + a + j * b)\n",
    "            dp = new \n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        for i in range(n + 1):\n",
    "            if s1 + s2 * i - dp[i] <= x:\n",
    "                return i \n",
    "        return - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j-1] + a + b * j)\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [0] * (n + 1) \n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda x: x[1]):\n",
    "            new = dp[:]\n",
    "            for j in range(1, n + 1):\n",
    "                new[j] = max(new[j], dp[j - 1] + a + j * b)\n",
    "            dp = new \n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        for i in range(n + 1):\n",
    "            if s1 + s2 * i - dp[i] <= x:\n",
    "                return i \n",
    "        return - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "\n",
    "        n = len(nums1)\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):\n",
    "\n",
    "            for j in range(n, 0, -1):\n",
    "\n",
    "                f[j] = max(f[j], f[j - 1] + a + b * j)\n",
    "\n",
    "\n",
    "\n",
    "        s1 = sum(nums1)\n",
    "\n",
    "        s2 = sum(nums2)\n",
    "\n",
    "        for t, v in enumerate(f):\n",
    "\n",
    "            if s1 + s2 * t - v <= x:\n",
    "\n",
    "                return t\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n=len(nums1)\n",
    "        dp=[0]*(n+1)\n",
    "        for a,b in sorted(zip(nums1,nums2),key=lambda z:z[1]):\n",
    "            for j in range(n,0,-1):\n",
    "                dp[j]=max(dp[j],dp[j-1]+a+b*j)\n",
    "        s1=sum(nums1)\n",
    "        s2=sum(nums2)\n",
    "        for t,v in enumerate(dp):\n",
    "            if s1+s2*t-v<=x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 建议直接看答案；本题难度有点高\n",
    "# https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/solutions/2374920/jiao-ni-yi-bu-bu-si-kao-ben-ti-by-endles-2eho/\n",
    "# dp[i][j]的定义为nums2的前i个数字经过j秒对总和减值贡献最大的值；其中nums2为升序排序\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums2)\n",
    "        dp = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda x:x[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                dp[j] = max(dp[j], dp[j-1] + a + b * j)\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t in range(n+1):\n",
    "            s = s1 + s2 * t\n",
    "            if s - dp[t] <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [0] * (n + 1)\n",
    "        # dp[0] = 0\n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda x: x[1]):\n",
    "            for j in range(n, 0, - 1):\n",
    "                dp[j] = max(dp[j], dp[j - 1] + a + b * j)\n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        for i in range(n + 1):\n",
    "            if s1 + s2 * i - dp[i] <= x:\n",
    "                return i \n",
    "        return - 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n=len(nums1)\n",
    "        dp=[0]*(n+1)\n",
    "        for a,b in sorted(zip(nums1,nums2),key=lambda z:z[1]):\n",
    "            for t in range(n,0,-1):#倒序遍历\n",
    "                dp[t]=max(dp[t],dp[t-1]+a+b*t)\n",
    "        s1,s2=sum(nums1),sum(nums2)\n",
    "        for t,val in enumerate(dp):\n",
    "            if s1+s2*t-val<=x:return t #小于等于\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n+1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda z: z[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j-1] + a + b * j)\n",
    "        \n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x: return t \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [0] * (n + 1) \n",
    "        for a, b in sorted(zip(nums1, nums2), key = lambda x: x[1]):\n",
    "            for j in range(n, 0, - 1):\n",
    "                dp[j] = max(dp[j], dp[j - 1] + a + b * j)\n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        for i in range(n + 1):\n",
    "            if s1 + s2 * i - dp[i] <= x:\n",
    "                return i \n",
    "        return - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        f = [0] * (n + 1)\n",
    "        for n1, n2 in sorted(zip(nums1, nums2), key=lambda x: x[1]):\n",
    "            for t in range(n, 0, -1):\n",
    "                f[t] = max(f[t], f[t - 1] + n1 + n2 * t)\n",
    "        for t in range(n + 1):\n",
    "            if s1 + t * s2 - f[t] <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n=len(nums1)\n",
    "        dp=[0]*(n+1)\n",
    "        for a,b in sorted(zip(nums1,nums2),key=lambda z:z[1]):\n",
    "            for t in range(n,0,-1):#倒序遍历\n",
    "                dp[t]=max(dp[t],dp[t-1]+a+b*t)\n",
    "        s1,s2=sum(nums1),sum(nums2)\n",
    "        for t,val in enumerate(dp):\n",
    "            if s1+s2*t-val<=x:return t #小于等于\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        dp = []\n",
    "        array = sorted(zip(nums2, nums1))\n",
    "        base = sum(nums1)\n",
    "        if base <= x:\n",
    "            return 0\n",
    "        dp.append(base)\n",
    "        update = sum(nums2)\n",
    "        dp.append(dp[-1] + update - array[0][0] - array[0][1])\n",
    "        if dp[-1]<=x:\n",
    "            return 1\n",
    "            \n",
    "        ans = 2*len(nums1)\n",
    "\n",
    "        # print(dp)\n",
    "        for i in range(1, len(array)):\n",
    "            dp2 = []\n",
    "            for j in range(i+2):\n",
    "                if j == 0:\n",
    "                    dp2.append(dp[0])\n",
    "                elif j == i+1:\n",
    "                    dp2.append(dp[j-1]+\\\n",
    "                        update-array[i][1] - j*array[i][0] )\n",
    "                else:\n",
    "                    dp2.append(min(dp[j], dp[j-1]+\\\n",
    "                        update-array[i][1]- j*array[i][0] ))\n",
    "                if dp2[-1] <= x:\n",
    "                    ans = min(ans, j)\n",
    "            dp = dp2\n",
    "            # print(i, dp)\n",
    "        return ans if ans < 2*len(nums1) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        f = [0] * (n + 1)\n",
    "        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] = max(f[j], f[j - 1] + a + b * j)\n",
    "\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t, v in enumerate(f):\n",
    "            if s1 + s2 * t - v <= x:\n",
    "                return t\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        s, ds = sum(nums1), sum(nums2)\n",
    "        if s <= x:\n",
    "            return 0\n",
    "        nums2_argsorted = sorted(range(n), key=lambda i: nums2[i])\n",
    "        f = [\n",
    "            [0 for _ in range(n + 1)],\n",
    "            [0 for _ in range(n + 1)],\n",
    "        ]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                prev = 0\n",
    "                if i > j:\n",
    "                    prev = f[(i - 1) & 1][j]\n",
    "                f[i & 1][j] = max(prev, f[(i - 1) & 1][j - 1] + nums1[nums2_argsorted[i - 1]] + j * nums2[nums2_argsorted[i - 1]])\n",
    "        for j in range(1, n + 1):\n",
    "            cur_s = s + j * ds - f[n & 1][j]\n",
    "            if cur_s <= x:\n",
    "                return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        # 经过k次操作之后，结果应该是s1 + k*s2 - V,问题转化为求V的最大值，进而转化为选出一个子序列，给每个元素分配一个系数（1，k)\n",
    "        # f[i][j] 表示前i个元素，长度为j的子序列，\n",
    "        # 组成的 a0 + 0*b0,a1 +1*b1,a2 + 2*b2, a3 + 3*b3....,aj + j*bj 最大值\n",
    "        # 由于选出的序列最后要被s1 + s2*k减去，a0到aj的和是固定值，所以随j增加，bj也应该增加，所以按照nums2排序，保证最大的j分给最大的nums2\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        arr = sorted(zip(nums1,nums2),key = lambda z:z[1])\n",
    "        for i in range(1,n + 1):\n",
    "            a,b = arr[i - 1]\n",
    "            for j in range(1,i + 1):\n",
    "                f[i][j] = max(f[i - 1][j],f[i - 1][j - 1] + a + j*b)\n",
    "        \n",
    "        s1,s2 = sum(nums1),sum(nums2)\n",
    "        for j in range(n + 1):\n",
    "            if s1 + j*s2 - f[n][j] <= x:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n=len(nums1)\n",
    "        #i*sums-fun(i)<=x\n",
    "        nums3=[]\n",
    "        dp=[[0]*n for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            nums3.append([nums2[i],nums1[i]])\n",
    "        nums3=sorted(nums3)\n",
    "        dp[0][0]=nums3[0][1]\n",
    "        dp[1][0]=nums3[0][0]+nums3[0][1]\n",
    "        for i in range(n):\n",
    "            if i>=1:\n",
    "                dp[1][i]=max(dp[1][i-1],nums3[i][0]+nums3[i][1])\n",
    "        if sum(nums1)<=x:\n",
    "            return 0\n",
    "        sums1=sum(nums1)\n",
    "        sums2=sum(nums2)\n",
    "        if sums2+sums1-dp[1][n-1]<=x:\n",
    "            return 1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(i-1,n):\n",
    "                dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+nums3[j][1]+nums3[j][0]*i)\n",
    "            if i*sums2+sums1-dp[i][n-1]<=x:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, s1, s2):\n",
    "        self.s1 = s1\n",
    "        self.s2 = s2\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        nodelist = []\n",
    "        nodenum = len(nums1)\n",
    "        sums1 = sum(nums1)\n",
    "        sums2 = sum(nums2)\n",
    "        for idx in range(nodenum):\n",
    "            nodelist.append(Node(nums1[idx], nums2[idx]))\n",
    "        dp = [[0 for _ in range(nodenum+1)] for _ in range(nodenum+1)]\n",
    "        nodelist.sort(key=lambda x:(x.s2, -x.s1))\n",
    "        # for item in nodelist:\n",
    "        #     print(item.s1, item.s2)\n",
    "        minj = nodenum+1\n",
    "        if x >= sums1:\n",
    "            return 0\n",
    "        for i in range(1, nodenum+1):\n",
    "            for j in range(i, 0, -1):\n",
    "                # if i==2 and j==1:\n",
    "                    # print('---',dp[i][j], dp[i-1][j], dp[i-1][j-1]+nodelist[i-1].s1+nodelist[i-1].s2, j)\n",
    "                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+nodelist[i-1].s1+nodelist[i-1].s2*j)\n",
    "                # print(i,j,dp[i][j],x,sums1+sums2*i)\n",
    "                if dp[i][j] + x >= sums1+sums2*j:\n",
    "                    minj = min(j, minj)\n",
    "        if minj == nodenum + 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return minj\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, A: List[int], B: List[int], x: int) -> int:\n",
    "        if sum(A) <= x:\n",
    "            return 0\n",
    "        N = len(A)\n",
    "        inds = sorted(list(range(N)), key=lambda i:B[i])\n",
    "        A = [None] + [A[i] for i in inds]\n",
    "        B = [None] + [B[i] for i in inds]\n",
    "        #  1 <= i1 , i2, ..., ik <= n\n",
    "        # (k-1)B[i1] + (k-2)B[i2] + ..., + (k-k)B[ik] + sum_{i!=ik}(A[i]+kB[i])\n",
    "        # sum_{t=1}^k(k-t)B[it] + sum_{i!=ik}(A[i]+kB[i])\n",
    "        # #  1 <= i1 < i2 < ... < ik <= n\n",
    "        # SA + kSB + sum_{t=1}^k(-A[it]-kB[it]+(k-t)B[it])\n",
    "        # SA + kSB + sum_{t=1}^k(-A[it]-tB[it])\n",
    "        # SA + kSB + T[n, k] <= x\n",
    "        # T[n, k] = min(T[n-1, k], -A[n]-kB[n]+T[n-1,k-1])\n",
    "        # T[n, 1] = min(T[n-1, 1], -A[n]-kB[n])\n",
    "        # T[n, n] = -A[n]-kB[n]+T[n-1,k-1]\n",
    "        # T[1, 1] = -A[1]-B[1]\n",
    "        T = [[None for _ in range(N+1)] for _ in range(N+1)]\n",
    "        SA = sum(A[1:])\n",
    "        SB = sum(B[1:])\n",
    "        for k in range(1, N+1):\n",
    "            for n in range(k, N+1):\n",
    "                if k == n:\n",
    "                    if k == 1:\n",
    "                        T[1][1] = -A[1]-B[1]\n",
    "                    else:\n",
    "                        T[n][n] = -A[n] - n*B[n] + T[n-1][n-1]\n",
    "                else:\n",
    "                    if k == 1:\n",
    "                        T[n][1] = min(T[n-1][1], -A[n]-B[n])\n",
    "                    else:\n",
    "                        T[n][k] = min(T[n-1][k], -A[n]-k*B[n] + T[n-1][k-1])\n",
    "            if SA + k*SB + T[n][k] <= x:\n",
    "                return k \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, A: List[int], B: List[int], x: int) -> int:\n",
    "        if sum(A) <= x:\n",
    "            return 0\n",
    "        N = len(A)\n",
    "        inds = sorted(list(range(N)), key=lambda i:B[i])\n",
    "        A = [None] + [A[i] for i in inds]\n",
    "        B = [None] + [B[i] for i in inds]\n",
    "        #  1 <= i1 < i2, ..., ik <= n\n",
    "        # (k-1)B[i1] + (k-2)B[i2] + ..., + (k-k)B[ik] + sum_{i!=ik}(A[i]+kB[i])\n",
    "        # SA + kSB + sum_{t=1}^k(-A[it]-kB[it]+(k-t)B[it])\n",
    "        # SA + kSB + sum_{t=1}^k(-A[it]-tB[it])\n",
    "        # SA + kSB + T[n, k] <= x\n",
    "        # T[n, k] = min(T[n-1, k], -A[n]-kB[n]+T[n-1,k-1])\n",
    "        # T[n, 1] = min(T[n-1, 1], -A[n]-kB[n])\n",
    "        # T[n, n] = -A[n]-kB[n]+T[n-1,k-1]\n",
    "        # T[1, 1] = -A[1]-B[1]\n",
    "        T = [[None for _ in range(N+1)] for _ in range(N+1)]\n",
    "        SA = sum(A[1:])\n",
    "        SB = sum(B[1:])\n",
    "        for k in range(1, N+1):\n",
    "            for n in range(k, N+1):\n",
    "                if k == n:\n",
    "                    if k == 1:\n",
    "                        T[1][1] = -A[1]-B[1]\n",
    "                    else:\n",
    "                        T[n][n] = -A[n] - n*B[n] + T[n-1][n-1]\n",
    "                else:\n",
    "                    if k == 1:\n",
    "                        T[n][1] = min(T[n-1][1], -A[n]-B[n])\n",
    "                    else:\n",
    "                        T[n][k] = min(T[n-1][k], -A[n]-k*B[n] + T[n-1][k-1])\n",
    "            if SA + k*SB + T[n][k] <= x:\n",
    "                return k \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [[ 0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        dp[0][1] = 0\n",
    "        for i, (a, b) in enumerate(sorted(zip(nums1, nums2), key=lambda x:x[1])):\n",
    "            for j in range(1, i+2):\n",
    "                dp[i+1][j] = max( dp[i][j], dp[i][j-1] + (a + b * j) )\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        for t in range(n+1):\n",
    "            if s1 + s2 * t - dp[n][t] <= x:\n",
    "                return t\n",
    "        return -1\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = sorted(zip(nums2, nums1))  # 按照nums2升序排列\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]  # dp[i][j]: 在num[:i]中操作了j个元素的最大下降\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                # 操作nums[i - 1]\n",
    "                dp[i][j] = dp[i - 1][j - 1] + nums[i - 1][0] * j + nums[i - 1][1]\n",
    "                # 不操作nums[i - 1]\n",
    "                if j < i:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j])\n",
    "        \n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        for t in range(n + 1):\n",
    "            if s1 + s2 * t - dp[n][t] <= x:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        if sum(nums1) <= x:\n",
    "            return 0\n",
    "        a = list(range(len(nums1)))\n",
    "        a.sort(key=lambda x: nums2[x])\n",
    "        nums1 = [nums1[i] for i in a]\n",
    "        nums2 = [nums2[i] for i in a]\n",
    "        basesum = sum(nums1)\n",
    "        daysum = sum(nums2)\n",
    "        dp=[[0]*(1+len(a)) for _ in range(len(a))]\n",
    "        for day in range(len(a)+1):\n",
    "            for ind in range(len(a)):\n",
    "                if day==0:\n",
    "                    dp[ind][day]=0\n",
    "                elif ind==0:\n",
    "                    dp[ind][day]=nums1[ind]+day*nums2[ind]\n",
    "                else:\n",
    "                    one=dp[ind-1][day]\n",
    "                    two=dp[ind-1][day-1]+nums1[ind]+day*nums2[ind]\n",
    "                    dp[ind][day]=max(one,two)\n",
    "            now = basesum + day * daysum - dp[len(a) - 1][day]\n",
    "            if now <= x:\n",
    "                return day\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        if sum(nums1) <= x:\n",
    "            return 0\n",
    "        a = list(range(len(nums1)))\n",
    "        a.sort(key=lambda x: nums2[x])\n",
    "        nums1 = [nums1[i] for i in a]\n",
    "        nums2 = [nums2[i] for i in a]\n",
    "        # 以上为预处理过程\n",
    "\n",
    "        basesum = sum(nums1)\n",
    "        daysum = sum(nums2)\n",
    "        dp=[[0]*(1+len(a)) for _ in range(len(a))]\n",
    "        for day in range(len(a)+1):\n",
    "            for ind in range(len(a)):\n",
    "                if day==0:\n",
    "                    dp[ind][day]=0\n",
    "                elif ind==0:\n",
    "                    dp[ind][day]=nums1[ind]+day*nums2[ind]\n",
    "                else:\n",
    "                    one=dp[ind-1][day]\n",
    "                    two=dp[ind-1][day-1]+nums1[ind]+day*nums2[ind]\n",
    "                    dp[ind][day]=max(one,two)\n",
    "            now = basesum + day * daysum - dp[len(a) - 1][day]\n",
    "            if now <= x:\n",
    "                return day\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        if sum(nums1) <= x:\n",
    "            return 0\n",
    "        a = list(range(len(nums1)))\n",
    "        a.sort(key=lambda x: nums2[x])\n",
    "        nums1 = [nums1[i] for i in a]\n",
    "        nums2 = [nums2[i] for i in a]\n",
    "        print(nums1,nums2)\n",
    "        dp=[[0]*(1+len(a)) for _ in range(len(a))]\n",
    "        for day in range(len(a)+1):\n",
    "            for ind in range(len(a)):\n",
    "                if day==0:\n",
    "                    dp[ind][day]=0\n",
    "                elif ind==0:\n",
    "                    dp[ind][day]=nums1[ind]+day*nums2[ind]\n",
    "                else:\n",
    "                    one=dp[ind-1][day]\n",
    "                    two=dp[ind-1][day-1]+nums1[ind]+day*nums2[ind]\n",
    "                    dp[ind][day]=max(one,two)\n",
    "        basesum = sum(nums1)\n",
    "        daysum = sum(nums2)\n",
    "\n",
    "        for k in range(1, len(nums1) + 1):\n",
    "            now = basesum + k * daysum - dp[len(a) - 1][k]\n",
    "            if now <= x:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n",
    "        nums1_sorted = [y for _, y in sorted(zip(nums2, nums1))]\n",
    "        nums2_sorted = sorted(nums2)\n",
    "\n",
    "        n = len(nums1)\n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+nums1_sorted[i-1]+nums2_sorted[i-1]*j)\n",
    "        for j in range(0, n+1):\n",
    "            if s1 + j*s2 - dp[n][j] <= x:\n",
    "                return j\n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
